1. Field of the Invention
This invention relates generally to a method and apparatus for decoding an error correction code and, more particularly, to a method and apparatus for decoding a Reed-Solomon code and to Euclidean algorithm arithmetic operation circuit that can be used therein.
2. Description of the Background
Conventionally, the decoding of the Reed-Solomon code is executed by steps involving: i) calculation of syndromes; ii) production of the error position polynomial .sigma.(x) and error evaluation polynomial .omega.(x); iii) estimation of the error position and error value; and iv) execution of the error correction.
The conventional decoding method using the solutions involving the roots of equations cannot be applied in situations requiring the correction of multiple errors consisting of five or more errors. In such situations a decoding method using the Euclidean algorithm is known for the correction of five or more errors. That is, the error position polynomial .sigma.(x) and error evaluation polynomial .omega.(x) are calculated by using the Euclidean algorithm.
In the apparatus for decoding the Reed-Solomon code using such Euclidean algorithm, there occurs a problem such that a reciprocal number, such as .alpha..sup.-9, is calculated to match with the highest degree coefficients of the dividend polynomial. More specifically, and assuming that the coefficients of the highest degree of two polynomials B(x) and S(x) are b and S, respectively, it is necessary to first calculate (b.times.S.sup.-1). To accomplish that calculation circuitry corresponding to a read only memory (ROM) or random access memory (RAM) is needed to obtain the reciprocal number, thereby causing the amount of hardware and circuitry to be increased beyond a desirable level.